"""
Problem 50: https://projecteuler.net/problem=50

Consecutive prime sum

The prime 41, can be written as the sum of six consecutive primes:
41 = 2 + 3 + 5 + 7 + 11 + 13

This is the longest sum of consecutive primes that adds to a prime below
one-hundred.

The longest sum of consecutive primes below one-thousand that adds to a prime,
contains 21 terms, and is equal to 953.

Which prime, below one-million, can be written as the sum of the most
consecutive primes?
"""

# _*_ conding:UTF-8 _*_
'''
@author = Kuperain
@email = kuperain@aliyun.com
@IDE = VSCODE Python3.8.3
@creat_time = 2022/5/19
'''


N = 1000000
PrimesT = [True]*N
PrimesT[0] = False
PrimesT[1] = False
for i in range(2, N):
    for k in range(i, (N-1)//i+1):
        PrimesT[i*k] = False

Primes = [n for n in range(N) if PrimesT[n]]
PrimesTotal = len(Primes)
print(f'Primes is ready, max is {Primes[-1]}.')


def solution(limit: int = 1000000) -> int:
    '''
    Which prime, below one-million, 
    can be written as the sum of the most consecutive primes?

    >>> print(solution(100))
    (41, 6, 2)
    >>> print(solution(1000))
    (953, 21, 7)
    '''
    mostPrime, lens = 2, 1
    longest = 1

    while sum(Primes[:lens]) < limit:

        # print(lens, mostPrime)
        lens += 1
        

        for i in range(PrimesTotal - lens):
            p = sum(Primes[i:i+lens])
            if p >= limit:
                break
            if PrimesT[p]:
                mostPrime = p
                longest = lens
                firstPrime = Primes[i]
                break

    return mostPrime, longest, firstPrime


if __name__ == "__main__":
    import doctest
    doctest.testmod(verbose=False)

    print(solution())
    # (997651, 543, 7)
